"""循环队列"""
"""循环队列
    enqueue O(1) 均摊
    dequeue O(1) 均摊
    get_front O(1)
    get_size  O(1)
    is_empty  O(1)
"""


class LoopQueueIsEmpty(ValueError):
    pass


class LoopQueue:
    def __init__(self, capacity=10):
        self.front = 0
        self.tail = 0
        self.size = 0  # 循环队列有个一为位置是浪费的
        self._queue = [None for _ in range(capacity + 1)]

    def get_capacity(self):
        # 返回循环队列的最大容量
        return len(self._queue) - 1

    def is_empty(self):
        return self.front == self.tail

    def get_size(self):
        # 返回当前循环队列中的元素数量
        return self.size

    def enqueue(self, element):
        if (self.tail + 1) % len(self._queue) == self.front:
            self.__resize(self.get_capacity() * 2)
        self._queue[self.tail] = element
        self.tail = (self.tail + 1) % len(self._queue)
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise LoopQueueIsEmpty("Can not dequeue from an empty loop queue")
        result = self._queue[self.front]
        self._queue[self.front] = None
        self.front = (self.front + 1) % len(self._queue)
        self.size -= 1
        if self.size == self.get_capacity() // 4 and self.get_capacity() // 2 != 0:
            self.__resize(self.get_capacity() // 2)
        return result

    def get_front(self):
        if self.is_empty():
            raise LoopQueueIsEmpty("loop queue is empty")
        return self._queue[self.front]

    def __resize(self, capacity):
        new_queue = [None for _ in range(capacity + 1)]
        i = 0
        while i < self.size:
            new_queue[i] = self._queue[(i + self.front) % len(self._queue)]
            i += 1
        self._queue = new_queue
        self.front = 0
        self.tail = self.size
